package StackAndQueue;

public class CircleQueue <E>{

	private E[] elements;
	private int size;
	private int front;
	private static final int DEFAULT_CAPACITY = 10;
	
	@SuppressWarnings("unchecked")
	public CircleQueue() {
		this.elements = (E[]) new Object[DEFAULT_CAPACITY];
		this.size = 0;
		this.front = 0;
	}

	public int size() {
		return size;
	}
	
	public boolean isEmpty() {
		return size == 0;
	}
	
	public E front() {
		return elements[front];
	}
	
	public void enQueue(E element) {
		// 扩容
		ensureCapacity();
		elements[size] = element;
		size++;
	}
	
	public E deQueue() {
		E elementE = elements[front];
		elements[front] = null;
		size--;
		term();
		return elementE;
	}
	
	@SuppressWarnings("unchecked")
	public void clear() {
		int capacity = (elements.length > DEFAULT_CAPACITY) ? elements.length : DEFAULT_CAPACITY;
		elements = (E [])new Object[capacity];
		size = 0;
		front = 0;
	}

	// 获取index位置在数组中的真实index.
	private int index(int index) {
		return (front + index) % elements.length;
	}
	
	// 扩容
	private <newCapacity> void ensureCapacity() {
		int oldCapacity = elements.length;
		int newCapacity = size + 1;
		if (oldCapacity >= newCapacity) {
			return;
		}
		
		newCapacity = oldCapacity + (oldCapacity >> 1);
		@SuppressWarnings("unchecked")
		E newElementsE[] = (E[]) new Object[newCapacity];
		for (int i = 0; i < size; i++) {
			newElementsE[i] = elements[index(i)];
		}
		elements = newElementsE;
		front = 0;
		System.out.println(oldCapacity + "扩容为" + newCapacity);
	}
	
	// 缩容
	private void term () {
        int oldCapacity = elements.length;
        int newCapacity = oldCapacity >> 1;
		front = index(1);
        if (size >= newCapacity || oldCapacity <= DEFAULT_CAPACITY ) return;

        @SuppressWarnings("unchecked")
		E[] newElements = ((E[]) new Object[newCapacity]);
        
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[index(i)];
        }
        
        elements = newElements;
        front = 0;
        System.out.println(oldCapacity + "缩容为" + newCapacity);
    }
}
